0% completed
Problem Statement
Given a binary tree, return true if it is an Even-Odd tree. Otherwise, return false.
The Even-odd tree must follow below two rules:
- At every
even-indexedlevel (starting from 0), all node values must beoddand arranged instrictly increasingorder fromlefttoright. - At every
odd-indexedlevel, all node values must beevenand arranged instrictly decreasingorder fromlefttoright.
Examples
Example 1
- Input:
1
/ \
10 4
/ \
3 7
- Expected Output:
true - Justification: The tree follows both conditions for each odd and even level. So, it is an
odd-eventree.
Example 2
Input:
5
/ \
9 3
/ \
12 8
- Expected Output:
false - Justification: Level 1 has Odd values 9 and 3 in decreasing order, but it should have even values. So, the tree is not an
odd-eventree.
Example 3
- Input:
7
/ \
10 2
/ \
12 8
- Expected Output:
false - Justification: At level 2 (even-indexed), the values are 12 and 8, which are even, but they should have odd values. So, the tree is not an
odd-eventree.
Constraints:
- The number of nodes in the tree is in the range [1, 105].
- 1 <= Node.val <= 106
Solution
To solve this problem, we can perform a level-order traversal (BFS) of the binary tree. During this traversal, we will keep track of the current level index to check whether it is even or odd. For each level, we will store the node values and verify the required conditions:
- If the level is even, the values should be odd and in strictly increasing order.
- If the level is odd, the values should be even and in strictly decreasing order.
This approach is efficient because it allows us to traverse each node once and check the conditions in a single pass. By maintaining a queue for BFS and lists for each level's values, we can ensure that all conditions are checked accurately.
Step-by-step Algorithm
- Initialize a queue for level-order traversal and add the root node to it.
- Initialize a variable
levelto 0 to keep track of the current level. - While the queue is not empty:
- Determine the number of nodes at the current level (
size). - Create an empty list (
values) to store the values of the nodes at the current level. - For each node in the current level:
- Remove the node from the queue.
- Add its value to the
valueslist. - If the node has a left child, add it to the queue.
- If the node has a right child, add it to the queue.
- Check the values collected at the current level:
- If the
levelis even:- Ensure all values are odd and strictly increasing.
- If the
levelis odd:- Ensure all values are even and strictly decreasing.
- If the
- If the values do not meet the required conditions, return
false. - Increment the
levelby 1.
- Determine the number of nodes at the current level (
- Return
trueif all levels meet the required conditions.
Algorithm Walkthrough
Input Tree:
1
/ \
10 4
/ \
3 7
Steps:
-
Initialization:
- Queue: [1]
- Level: 0
-
Level 0:
- Size: 1
- Values: []
- Process node 1:
- Queue: []
- Values: [1]
- Add left child (10) to the queue
- Add right child (4) to the queue
- Check values for even level:
- Values: [1] (all odd and strictly increasing)
- Increment level: 1
-
Level 1:
- Size: 2
- Values: []
- Process node 10:
- Queue: [4]
- Values: [10]
- Add left child (3) to the queue
- Add right child (7) to the queue
- Process node 4:
- Queue: [3, 7]
- Values: [10, 4]
- Check values for odd level:
- Values: [10, 4] (all even and strictly decreasing)
- Increment level: 2
-
Level 2:
- Size: 2
- Values: []
- Process node 3:
- Queue: [7]
- Values: [3]
- Process node 7:
- Queue: []
- Values: [3, 7]
- Check values for even level:
- Values: [3, 7] (all odd and strictly increasing)
- Increment level: 3
-
Completion:
- Queue is empty, all levels meet the required conditions.
- Return
true.
Code
Complexity Analysis
Time Complexity
The algorithm performs a level-order traversal of the binary tree, which means it visits each node exactly once. Therefore, the time complexity is
Space Complexity
The space complexity is determined by the maximum number of nodes at any level in the binary tree. In the worst case, this can be
On this page
Problem Statement
Examples
Solution
Step-by-step Algorithm
Algorithm Walkthrough
Code
Complexity Analysis
Time Complexity
Space Complexity